#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include "bst.h"

Tree_Node *
search(Tree_Node *root, Element elem)
{
	if(root==NULL || root->value==elem)
		return root;
	if(root->value >= elem)
		return search(root->left, elem);
	else
		return search(root->right, elem);
}

void
insert(Tree_Node **proot, Element elem)
{
	Tree_Node *node;
	if((node = malloc(sizeof(Tree_Node))) == NULL) {
		fprintf(stderr, "malloc error in insert\n");
		exit(1);
	}
	node->value = elem;
	node->left = node->right = node->parent = NULL;
	Tree_Node **pnode = proot;
	while(proot && *pnode) {
		node->parent = *pnode;
		if((*pnode)->value > elem) 
			pnode = &((*pnode)->left);
		else 
			pnode = &((*pnode)->right);
	}
	*pnode = node;
}

void
inorder(Tree_Node *root, void (*visit)(Tree_Node *node))
{
	if(root != NULL) {
		inorder(root->left, visit);
		visit(root);
		inorder(root->right, visit);
	}
}

Tree_Node *
minimum(Tree_Node *root)
{
	if(root==NULL)
		return NULL;
	Tree_Node *min = root;
	while(min->left != NULL)
		min = min->left;
	return min;
}

Tree_Node *
maximum(Tree_Node *root)
{
	if(root==NULL)
		return NULL;
	Tree_Node *max = root;
	while(max->right != NULL)
		max = max->right;
	return max;
}

Tree_Node *
successor(Tree_Node *node)
{
	//right-child exist
	if(node->right != NULL)
		return minimum(node->right);
	//right-child doesn't exist
	Tree_Node *c = node;
	Tree_Node *p = c->parent;
	while(p!=NULL && c==p->right) {
		c = p;
		p = c->parent;
	}
	return p;
}

Tree_Node *
predecessor(Tree_Node *node)
{
	//left-child exist
	if(node->left != NULL)
		return maximum(node->left);
	//left-child doesn't exist
	Tree_Node *c = node;
	Tree_Node *p = c->parent;
	while(p!=NULL && c==p->left) {
		c = p;
		p = c->parent;
	}
	return p;
}

void
destroy(Tree_Node *root)
{
	if(root == NULL)
		return;
	destroy(root->left);
	destroy(root->right);
	free(root);
}

static int
max(int a, int b)
{
	return a>b ? a : b;
}

int
height(Tree_Node *root)
{
	if(root==NULL || (root->left==NULL && root->right==NULL))
		return 0;
	else
		return max(height(root->left)+1, height(root->right)+1);
}

void
deletefrom(Tree_Node **proot, Element elem)
{
	Tree_Node *target, *del, *tmp;
	if((target = search(*proot, elem)) == NULL) {
		fprintf(stderr, "Find no node for: %d\n", elem);
		return;
	}
	//set 'del' to be the node for deleting, at least one of its children is NULL
	if(target->left != NULL && target->right != NULL)
		del = successor(target);
	else
		del = target;
	if(del->left != NULL)
		tmp = del->left;
	else if(del->right != NULL)
		tmp = del->right;
	else
		tmp = NULL;
	
	if(del->parent != NULL) {
		if(del == del->parent->left) {
			del->parent->left = tmp;
			if(tmp != NULL)
				tmp->parent = del->parent;
		}
		else {
			del->parent->right = tmp;
			if(tmp != NULL)
				tmp->parent = del->parent;
		}
	} else {//del is root
		*proot = tmp;
		if(tmp != NULL)
			tmp->parent = NULL;
	}

	if(del != target) { //copy the key and satellite data
		target->value = del->value;
	}

	free(del);
}

void 
left_rotate(Tree_Node **root, Tree_Node *node)
{
	/*
	printf("node: %d\n", node->value);
	printf("node parent: %d\n", node->parent==NULL?-1:node->parent->value);
	printf("node left child: %d\n", node->left==NULL?-1:node->left->value);
	printf("node right child: %d\n", node->right==NULL?-1:node->right->value);
	*/
	Tree_Node *nd_right = node->right; //set nd_right
	if(nd_right == NULL) {
		fprintf(stderr, "Can't Left Rotate\n");
		return;
	}
	nd_right->parent = node->parent;
	if(node->parent == NULL)
		*root = nd_right;
	else {
		if(node == node->parent->left)
			node->parent->left = nd_right;
		else
			node->parent->right = nd_right;
	}
	Tree_Node *nd_right_left = nd_right->left;
	nd_right->left = node;
	node->parent = nd_right;
	node->right = nd_right_left;
	if(nd_right_left != NULL)
		nd_right_left->parent = node;
	/*
	printf("node: %d\n", node->value);
	printf("node parent: %d\n", node->parent==NULL?-1:node->parent->value);
	printf("node left child: %d\n", node->left==NULL?-1:node->left->value);
	printf("node right child: %d\n", node->right==NULL?-1:node->right->value);
	*/
}

void
right_rotate(Tree_Node **root, Tree_Node *node)
{	
	/*
	printf("node: %d\n", node->value);
	printf("node parent: %d\n", node->parent==NULL?-1:node->parent->value);
	printf("node left child: %d\n", node->left==NULL?-1:node->left->value);
	printf("node right child: %d\n", node->right==NULL?-1:node->right->value);
	*/
	Tree_Node *nd_left = node->left; //set nd_left
	if(nd_left == NULL) {
		fprintf(stderr, "Can't Right Rotate\n");
		return;
	}
	nd_left->parent = node->parent;
	if(node->parent == NULL)
		*root = nd_left;
	else {
		if(node == node->parent->left)
			node->parent->left = nd_left;
		else
			node->parent->right = nd_left;
	}
	Tree_Node *nd_left_right = nd_left->right;
	nd_left->right = node;
	node->parent = nd_left;
	node->left = nd_left_right;
	if(nd_left_right != NULL)
		nd_left_right->parent = node;
	/*
	printf("node: %d\n", node->value);
	printf("node parent: %d\n", node->parent==NULL?-1:node->parent->value);
	printf("node left child: %d\n", node->left==NULL?-1:node->left->value);
	printf("node right child: %d\n", node->right==NULL?-1:node->right->value);
	*/
}
